1. Field of the Invention
The present invention relates to a method of retrieving an optimum case for a given problem from a case data base and inferring a solution of the problem by using the retrieved case, and a system therefor.
2. Description of Related Art
Case information means data composed of data representing a problem and data representing a solution of the problem or a way to solve the problem, i.e., a solving method. One of the objects of using case information is such that a system retrieves a solved case of a problem similar to a problem to be currently solved (an analogous case) and a user refers to the solution or the solving method in that case. Another object of using case information is such that the system retrieves the analogous case and further performs an inference by using the analogous case, thereby to obtain a solution of a current problem. Thus, a technical subject for using case information is to develop a method of retrieving an analogous case which furnishes with much information for the current problem out of a plurality of accumulated cases and a method of solving the problem by using the analogous case.
A conventional method of retrieving and using an analogous case is discussed in "Case-Based Reasoning Workshop", (1988) pp. 21-30, for instance. A problem is represented therein by using goals which are desired to achieve in the problem and constraints which are to be satisfied in solving the problem. First, the following processing method has been proposed for analogous case retrieval.
(1) Goals of the current problem and goals of the problem in a case are compared with each other, so as to select cases including plenty of common goals.
(2) When a plurality of cases are obtained in the processing (1), the constraints of the current problem and the constraints of the problem in the case, i.e., the case problem are compared with one another so as to select cases which hold one or more important constraints in common. (However, information relating to significance of constraints is given to the system in advance.)
This system is based on the following thoughts in substance.
(1) The more features the current problem and the case problem includes in common, the more similar those cases are.
(2) In order to reflect not only the number of features held in common but also the significance thereof in processing, weighting of features is applied.
Further, the following processing method has been proposed for the use of the analogous case.
(1) Regarding a partial problem represented by a feature group which is shared by the current problem and the case problem as a partial problem common to the current problem and the case problem, a portion corresponding to the partial problem is taken out of the solution of the case.
(2) The taken out partial solution is modified so as to be adapted to the current problem and is used as a part of the solution of the current problem.
A plurality of partial problems involved in one problem are not independent of one another in various fields. Namely, a plurality of features representing the problem are not independent of one another. Since an influence relation, an interference relation or a dependency relation among these features has not been considered in the conventional system, it has happened sometimes that a case having less utility for solving the current problem is retrieved.
For example, positioning of individual equipment may be considered as a partial problem in a layout problem in a computer room. Here, the positioning of a card reader and a card puncher for katakana characters (hereinafter referred simply as a card puncher) depends on the positioning of a console display. That is, an influence relation exists among these partial problems.
Now, when a set of equipment names to be arranged are used as a feature group representing the problem, it is assumed that the current problem is the positioning problem represented by {card reader, card puncher, console display}, viz., the layout problem of a card reader, a card puncher and a console display. Further, it is assumed that the case includes a card reader, and a card puncher, but does not include a console display (for example, it is arranged in another room sometimes). In this case, the current problem and the case problem include a card reader and a card puncher in common, but the positioning of these units in the case is not applicable in the current problem. Because, the layout of the card reader and the card puncher varies depending on existence of the console display.
On the other hand, it is assumed that the current problem includes a card reader and a card puncher and does not include a console display. Further, it is assumed that the case problem includes a card reader, a card puncher and a console display. On this occasion, a case can neither be used for the positioning of the card reader and the card puncher because of the same reason as described previously. In this manner, the solution of the case cannot necessarily be used on common features. Therefore, the case including much common features is not necessarily a useful case.
Further, the existence of the console display determines usefulness of a case in the above-described example. However, the console display is not important sometimes depending on the problem. For example, the positioning of a communication control processor and a power supply unit does not depend on the positioning of the console display. Accordingly, it is not important whether the case includes a console display or not when a case is retrieved in the layout thereof. In this manner, the significance of the features depends on the combination of a problem and a case, and is not fixed. Thus, a useful case cannot necessarily be retrieved even when weighting of features is used.
According to a conventional method of retrieving a case, a case of little usefulness is retrieved sometimes as described above. Thus, there have been such problems as waste of time due to repetition of retrieval and mistakes in determination based on an inappropriate case.
Further, in a conventional method of using a case, all partial solutions of cases corresponding to common features in a current problem and a case problem have been used as the partial solution of the current problem. Thus, it has been required to correct the effect of influence among features. For example, since the layout in a case of a card reader and a card puncher cannot be used as it is under the influence of a console display, the layout thereof has been required to be corrected in above-described example. Thus, in a conventional method of using a case, there have been such problems as complicated processing is required for correcting influence among features, the development period and the development cost for an inference system gets longer and higher, and performance and reliability are lowered.
One of the techniques for solving the above-described problems has been proposed by YOSHIURA et al., YOSHIURA being an inventor of the present application, at the national convention of Information Processing Society of Japan. The proposal has been made in "An Approach to Knowledge Acquisition Bottleneck using Case-Based Reasoning (1),--Case Utilization Method--", Information Processing Society of Japan, the national convention collection of papers, 4D-7, pp. 274-275, March (1990) and "An approach to knowledge Acquisition Bottleneck using Case-Based Reasoning (2),--Application to Computer Room Layout Problem--", Information processing Society of Japan, the national convention collection of papers, 4D-8, pp. 276-277, March (1990).
The technique proposed by YOSHIURA et al. will be explained hereinafter. In this technique, dependency relation information is referred to, features that are to be included in a case to be retrieved and features that should not be included therein are obtained and cases are retrieved from a case base using these features.
In accordance with a case and features to be included in a case to be retrieved, a solution of a current problem is obtained the cases by using a portion, of a solution in the case, corresponding to a partial problem represented by these features.
With reference to FIG. 14, a variable T substituted for dependency relation information between features and a variable FI substituted for a feature set which should be included in an analogous case are adopted as input arguments. A portion related to the inputted current problem among dependency relation information is substituted for the variable T as an initial value. Further, the whole feature set of the current problem is substituted for the variable FI.
The contents of processing will be described hereinafter. In a step 1301, a feature set which should not be included in an analogous case is obtained and substituted for a variable FE. Here, a procedure P.sub.roc is a procedure for obtaining a feature set which should not be included in an analogous case with the feature set FI to be included in an analogous case as an argument. The contents of processing in the procedure P.sub.roc will be described in detail later with reference to FIG. 15.
In a step 1302, a case including all features in the variable FI and no feature in the variable FE is retrieved from a case base. An appropriate case can be retrieved by using variables FI and FE. In a step 1303, the existence of a pertinent case is determined. When a case exists, the case is delivered to a controller in a step 1304 and processing is stopped thereafter. When a case does not exist, the processing proceeds to a step 1305.
In a step 1305, a list of features which do not appear in the variable T among features of a problem is formed, which is substituted for a variable L. The variable L is a list of features to be removed from the variable FI.
In a step 1306, it is determined whether the variable L is empty or not. If the variable L is empty, there is no feature to be removed from the variable FI, that is, a new variable FI cannot be obtained. Therefore, the processing is brought to a standstill and returned. If the variable L is not empty, the processing proceeds to a step 1307.
In the step 1307, one of the features is taken out of the variable L and substituted for a variable F. In a step 1308, the taken out feature is removed from the variable L. In a step 1309, the result obtained by removing the variable F from the variable FI is substituted for a variable FI'. The variable FI' is a new candidate of a feature set to be included in an analogous case. When an analogous case is retrieved using the variable FI', the feature set held in common by the problem and the analogous case is the variable FI'. Here, the feature of the variable F removed from the variable FI does not appear in the dependency relation information T. Therefore, the variable F is not the feature exerting an influence upon the partial problem corresponding to the variable FI'. Thus, features which exert an influence upon the partial problem corresponding to the variable FI' and are included in the feature set of the inputted problem are all included in the variable FI', viz., the feature set of the retrieved analogous case.
In a step 1310, a table showing the result obtained by removing the variable F from the variable T is substituted for a variable T'. In a step 1311, the present processing is executed recursively with the sets FI' and T' as arguments in place of the sets FI and T. When an analogous case is found in the process of this recursive execution, the analogous case is outputted in the step 1304, and the operation is stopped. When an analogous case is not found, the processing returns to the step 1311 through the step 1306. As a result, the processing proceeds to the step 1306. At this time, in the steps 1306 to 1310, the features that are different from the last occasion are removed from the set FI, and a case is retrieved again in the step 1311. When every possibility becomes exhausted, Yes is determined in the step 1306 in the processing at the top level, and the whole processing returns to the controller.
FIG. 15 shows the operation of the procedure P.sub.roc of the step 1301 shown in FIG. 14. The procedure P.sub.roc is for obtaining a feature set which should not be included in an analogous case with the feature set FI which should be included in an analogous case as an argument. In a step 1401, the set FI is substituted for a set S.
In a step 1402, dependency feature information having no relation with the current problem is obtained from a group of dependency feature information. To be concrete, dependency feature information including what is not the feature of the current problem is found, and a table composed of the information is formed and substituted for the variable T1.
In a step 1403, dependency feature information with the right member of which is included in the variable S among the variable T1 is taken out, and a table consisting of such information is generated and substituted for the variable T1'. In a step 1404, a set of features included in the variable T1' is obtained and substituted for the variable S'. A feature set exerting an influence directly upon a partial problem corresponding to the variable FI is substituted for the variable S'.
What is to be noted here is that there is the possibility that features exert an influence indirectly upon the solution of the problem even if there were no dependency feature information including features and problems. For example, when A exerts an influence upon B and B exerts an influence upon C, a dependency relation that A exerts an influence upon C exists.
Thus, it is needed to obtain a feature set which exerts an influence upon a partial problem corresponding to the variable FI including such an indirect influence. For that purpose, it is only required to repeat processings in the steps 1403 and 1404 until the variable S converges.
In a step 1405, convergence is determined. In the case of convergence, that is, when features which are not included in the variable S do not exist in the variable S', the set in which features in the variable FI have been removed from the variable S is returned to the main routine shown in FIG. 14 as a feature set which should not be included in an analogous case. In the case of no convergence, that is, when features which are not included in the variable S exist in the variable S', a union of the sets S and S' is obtained a new as a set S in a step 1407 and the processing is returned to the step 1403.
As described above, according to this technique, the set FI is initialized to the whole feature set of the current problem. The case corresponding to at least a part of the feature set common to the case problem and the current problem can be used for solving the current problem. Hence, the initial value of the set FI is the largest possible set as the use portion. The set substituted for the set FI is reduced one element at a time, and retrieval of the case is applied on all such occasions in the step 1309. As a result, a case in which the use portion reaches the maximum is retrieved. A part corresponding to a partial problem represented by the set FI among the solutions of the case is the part that can be used without compensation for the influence.
In the next place, another case retrieval processing which has been proposed at the same time will be explained. In the case retrieval processing, a part which is related to the current problem is picked out of the dependency relation information table first and is substituted for the variable T. Further, the total number of the features of the problem is substituted for a variable N.
With reference to FIG. 16, a variable I is initialized in a step 1501. This variable I is a counter for selecting one feature from a feature set of a problem. In a step 1502, it is determined whether all the featues have been selected completely or not. In the case of Yes in the step 1502, the processing is returned assuming that there was no analogous case. In the case of No, the processing proceeds to a step 1503.
In the step 1503, the variable I is increased by "1" only. In a step 1504, the Ith feature in the feature set of the problem is selected, and a set having the Ith feature as an element is set in the set S1. In a step 1505, a table in which dependency feature information with a part of the variable set T included in the set S1 is collected is set as a set T2. In a step 1506, a set composed of features included in the set T2 is set as a variable set S2. With above-described processing, a feature set which exerts an influence directly upon a partial problem corresponding to the set S1 is substituted for the set S2.
In a step 1507, a union of the sets S1 and S2 is set as a set S1'. Here, in order to obtain a feature set which exerts an influence indirectly upon the set S1, the steps 1505 to 1507 are repeated until the sets S1 and S1' converge. In a step 1508, convergence is determined. In the case of convergence, that is, when S1=S1', the processing proceeds to a step 1510. In the case of no convergence, the set S1 is replaced with the set S1' in a step 1509, and the processing is returned to the step 1505.
As described, all the features included in the current problem among those features that exert an influence upon a partial problem corresponding to the set S1 are included in the set S1. This set S1 becomes a feature set to be included in an analogous case. When the analogous case is retrieved using the set S1, the feature set included in common in the analogous case and the problem is the set S1. Accordingly, those features that exert an influence upon a partial problem corresponding to the feature set included in common in the analogous case and the problem and are included in the problem are all included in the analogous case, too.
In a step 1510, the procedure P.sub.roc shown in FIG. 15 is invoked with the set S1 as an argument, and the feature set which should not be included in the analogous case is obtained and set as the variable set FE.
In a step 1511, cases including the set S1 and including no set FE are retrieved from the case base. In a step 1512, it is determined whether an analogous case has been found or not. When it is found, the analogous case is delivered to the controller in a step 1513, thus completing retrieval processing. When it is not found, the processing is returned to the step 1502, and above-described processing is repeated using other partial problems.
(a) An Approach to Knowledge Acquisition Bottleneck using Case-Based Reasoning (1),--Case Utilization System--:
a new system of case-based inference for solving a problem based on past cases. In general, case-based inference consists of processes for retrieving the most effective case for solving a current problem among a plurality of cases (case retrieval processing) and processes for solving the problem based on the retrieved cases (case using processing). In the case using processing of the proposed system, a portion which is applicable as it is to the current problem is brought down, and that portion is used. In the case retrieval processing, a case in which a solvable portion on the current problem reaches the maximum is retrieved. As to the means of realization, the knowledge related to the problem and the relation among elements of the cases is used, the problem and the cases are divided into parts, respectively, and the influence relation among the parts is analyzed, thereby to retrieve an objective case and further determine the usable parts therein.
(b) An Approach to Knowledge Acquisition Bottleneck using Case-Based Reasoning (2),--Application to Computer Room Layout Problem--:
a computer room layout system using above-described system (a system of arranging various equipments in a computer room) is described.
As described above, according to above-described two proposed techniques, the cases usable without compensation for the influence can be retrieved. As it is apparent from FIGS. 14 to 16, however, processings are determined consecutively on respective features and unnecessary elements are reduced one by one. Thus, there has been a problem that processing for retrieving usable cases is complicated and takes a long period of time.
Furthermore, in a conventional method of retrieving and using a case, it has been assumed that all the solutions of a current problem are obtained from a case. Actually, however, a user desires sometimes to designate a part of the solution of the current problem or to obtain a part of the solution by means of another inference system using no cases. Such requirements could not be met with a conventional system of retrieving and using a case.